#include "string_array.h"

using namespace std;

void myStr::initStorage(int len) {
    length = len;
    data = new char[length + 1];
    data[length] = '\0';
    next = nullptr;
    nextVal = nullptr;
}

void myStr::copyFrom(const myStr& S) {
    for (int i = 0; i <= length; ++i) {
        data[i] = S.data[i];
    }
    if (S.next != nullptr) {
        next = new int[length];
        for (int i = 0; i < length; ++i) {
            next[i] = S.next[i];
        }
    }
    if (S.nextVal != nullptr) {
        nextVal = new int[length];
        for (int i = 0; i < length; ++i) {
            nextVal[i] = S.nextVal[i];
        }
    }
}

void myStr::releaseNextBuffers() {
    delete[] next;
    delete[] nextVal;
    next = nullptr;
    nextVal = nullptr;
}

//有参构造字符串
myStr::myStr(const char* ch) {
    int len = 0;
    if (ch != nullptr) {
        while (ch[len] != '\0') {
            ++len;
        }
    }
    initStorage(len);
    for (int i = 0; i < length; ++i) {
        data[i] = ch[i];
    }
    data[length] = '\0';
}

//拷贝构造字符串
myStr::myStr(const myStr& S) {
    initStorage(S.length);
    if (S.length == 0) {
        data[0] = '\0';
        return;
    }
    copyFrom(S);
}

//销毁字符串
myStr::~myStr() {
    delete[] data;
    releaseNextBuffers();
    data = nullptr;
    length = 0;
}

//求next数组
void myStr::kmp_next() {
    releaseNextBuffers();
    if (length == 0) return;
    next = new int[length];
    int i = 0, j = 0;
    next[0] = 0;
    while (i < length) {
        if (j == 0 || data[i] == data[j-1]) {
            i++;
            j++;
            if (i >= length)break;
            next[i] = j;
        }
        else {
            j = next[j-1];
        }
    }
}


//求nextVal数组
void myStr::kmp_nextVal() {
    if (length == 0) {
        releaseNextBuffers();
        return;
    }
    if (next == nullptr) {
        kmp_next();
    }
    if (nextVal != nullptr) {
        delete[] nextVal;
    }
    nextVal = new int[length];
    nextVal[0] = 0;
    for (int i = 1; i < length; ++i) {
        int prefixIdx = next[i]-1;
        if (data[i] == data[prefixIdx]) {
            nextVal[i] = nextVal[prefixIdx];
        }
        else
            nextVal[i] = next[i];
    }
}


//子串替换
bool replaceStr(myStr& S, const int& start, const myStr& T, const myStr& V) {
    if (S.length == 0 || T.length == 0 || start < 1 || start > S.length) {
        return false;
    }
    if (S.length < T.length) return false;
    int pos = -1;
    for (int i = start - 1; i <= S.length - T.length; ++i) {
        bool matched = true;
        for (int j = 0; j < T.length; ++j) {
            if (S.data[i + j] != T.data[j]) {
                matched = false;
                break;
            }
        }
        if (matched) {
            pos = i + 1;
            break;
        }
    }
    if (pos == -1) return false;
    int shift = V.length - T.length;
    if (shift != 0) {
        char* newData = new char[S.length + shift + 1];
        for (int i = 0; i < pos - 1; ++i)
            newData[i] = S.data[i];
        for (int i = 0; i < V.length; ++i)
            newData[pos - 1 + i] = V.data[i];
        for (int i = pos - 1 + T.length; i <= S.length; ++i)
            newData[i + shift] = S.data[i];
        delete[] S.data;
        S.data = newData;
    }
    else {
        for (int i = 0; i < V.length; ++i)
            S.data[pos - 1 + i] = V.data[i];
    }
    S.length += shift;
    S.data[S.length] = '\0';
    S.releaseNextBuffers();
    return true;
}


//BF匹配
int simpleMatch(const myStr& S, const myStr& T) {
    if (T.length == 0) return 1;
    if (S.length < T.length) return -1;
    for (int i = 0; i <= S.length - T.length; ++i) {
        int j = 0;
        while (j < T.length && S.data[i + j] == T.data[j]) {
            ++j;
        }
        if (j == T.length) {
            return i + 1;
        }
    }
    return -1;
}

//kmp匹配
int kmpMatch(const myStr& S, const myStr& T) {
    if (T.length == 0) return 1;
    if (S.length < T.length) return -1;
    myStr pattern(T);
    pattern.kmp_nextVal();
    const int* nextArr = pattern.nextVal != nullptr ? pattern.nextVal : pattern.next;
    int i = 0;
    int j = 0;
    while (i < S.length && j < pattern.length) {
        if (S.data[i] == pattern.data[j]) {
            ++i;
            ++j;
        }
        else if (j == 0) {
            ++i;
        }
        else {
            j = nextArr[j - 1];
        }
    }
    if (j >= pattern.length) {
        return i - pattern.length + 1;
    }
    return -1;
}

//输出字符串
void myStr::print(){
    for(int i = 0; i < this->length; i++)
        cout << this->data[i];

    cout << endl;
}

//输出next数组
void myStr::printNext(){
    if (next == nullptr && length > 0)
        kmp_next();
    for(int i = 0; i < length; i++)
        cout << next[i];
    cout << endl;
}

//输出nextVal数组
void myStr::printNextVal(){
    if (nextVal == nullptr && length > 0)
        kmp_nextVal();
    for(int i = 0; i < length; i++)
        cout << nextVal[i];
    cout << endl;
}

//无参构造矩阵
myMatrix::myMatrix() {
    rowNum = 0;
    colNum = 0;
    nodeNum = 0;
    nodeList = nullptr;
}

//有参构造矩阵
myMatrix::myMatrix(const int& rNum, const int& cNum, const int& nNum, const int* arr) {
    rowNum = rNum;
    colNum = cNum;
    nodeNum = nNum;
    if (nodeNum > 0) {
        this->nodeList = new matrixNode[nNum];
        for (int i = 0; i < nNum; ++i) {
            nodeList[i].row = arr[3 * i];
            nodeList[i].col = arr[3 * i + 1];
            nodeList[i].value = arr[3 * i + 2];
        }
    }
    else {
        nodeList = nullptr;
    }
}

//拷贝构造矩阵
myMatrix::myMatrix(const myMatrix& M) {
    this->rowNum = M.rowNum;
    this->colNum = M.colNum;
    this->nodeNum = M.nodeNum;
    if (nodeNum > 0) {
        this->nodeList = new matrixNode[M.nodeNum];
        for (int i = 0; i < M.nodeNum; i++) {
            this->nodeList[i].row = M.nodeList[i].row;
            this->nodeList[i].col = M.nodeList[i].col;
            this->nodeList[i].value = M.nodeList[i].value;
        }
    }
    else {
        this->nodeList = nullptr;
    }
}

//销毁矩阵
myMatrix::~myMatrix() {
    rowNum = 0;
    colNum = 0;
    nodeNum = 0;
    delete[]nodeList;
    nodeList = nullptr;
}

//矩阵快速转置
void myMatrix::FastTransposeSMatrix(myMatrix& T) {
    T.rowNum = this->colNum;
    T.colNum = this->rowNum;
    T.nodeNum = this->nodeNum;
    delete[] T.nodeList;
    T.nodeList = nullptr;
    if (nodeNum == 0) return;
    T.nodeList = new matrixNode[T.nodeNum]; 
    const int cool = colNum + 1;
    int* num = new int[cool]();
    int* cpot = new int[cool]();  
    for (int i = 0; i < nodeNum; ++i) {
        num[nodeList[i].col]++; 
    }
    cpot[0] = 0;
    for (int c = 1; c <= colNum; ++c) { 
        cpot[c] = cpot[c - 1] + num[c - 1]; 
    }
    for (int i = 0; i < nodeNum; ++i) {
        int col = nodeList[i].col;
        int idx = cpot[col];
        T.nodeList[idx].row = nodeList[i].col;
        T.nodeList[idx].col = nodeList[i].row;
        T.nodeList[idx].value = nodeList[i].value;
        cpot[col]++;
    }
    delete[] num;
    delete[] cpot;
}

//输出矩阵
void myMatrix::printMatrix(){
    cout << rowNum << "," << colNum << "," << nodeNum << endl;

    for(int i = 0; i < nodeNum; i++)
        cout << nodeList[i].row << "," << nodeList[i].col << "," << nodeList[i].value << endl;
}
